package com.leetCode.problem;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-03 14:11:15
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-03     张李鑫                     1.0         1.0 Version
 */
public class Problem10 {
    /**
     * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
     * <p>
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/regular-expression-matching
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */


    public static boolean isMatch(String s, String p) {
        return process(s.toCharArray(), p.toCharArray(), 0, 0);
    }

    private static boolean process(char[] s, char[] p, int sIndex, int pIndex) {

        if (pIndex == p.length) {
            if (sIndex == s.length) {
                return true;
            } else {
                return false;
            }
        }
        if (s.length == sIndex) {
            return true;
        }
        if (p[pIndex] == '.') {
            return process(s, p, sIndex + 1, pIndex + 1);
        }
        if (p[pIndex] == '*') {
            return s[sIndex] == p[pIndex - 1] && process(s, p, sIndex + 1, pIndex);
        }
        if (p[pIndex] != '.' && p[pIndex] != '*') {
            return s[sIndex] == p[pIndex] && process(s, p, sIndex + 1, pIndex + 1);
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aaa", "c*a*b"));
    }
}
